1. Field of the Invention
The present invention relates generally to a mobile communication system, and in particular, to an apparatus and method for memory sharing between an interleaver and a deinterleaver in a turbo decoder.
2. Description of the Related Art
In general, a digital communication system supports forward error correction (FEC) so that a receiver can correctly restore received data even though a transmission error has occurred in the received data. For the forward error correction, the commercialized CDMA (Code Division Multiple Access) communication system, e.g., the IS-95 system uses convolutional codes having strong restitution force against burst errors, and the next generation mobile communication system, e.g., the CDMA2000 or UMTS (Universal Mobile Telecommunications System) system uses turbo codes having more powerful error restitution force.
Now, a structure of a turbo coder will be described herein below with reference to FIG. 1.
FIG. 1 is a block diagram illustrating a structure of a common turbo coder. The turbo coder includes constituent coders supporting recursive systematic codes. Referring to FIG. 1, as a signal X(t), generated by adding CRC (Cyclic Redundancy Check) and tail bits to an input signal, is input to the turbo coder, namely, X(t) is provided in parallel to a first constituent coder 100 and a second constituent coder 150. The first constituent coder 100 and the second constituent coder 150 are activated by their control switches. The input to the second constituent coder 150 includes information bits interleaved by an interleaver 130. Upon receiving the input signal, the first constituent coder 100 and the second constituent coder 150 output X(t), Y0(t), Y1(t), Y′0(t), Y′1(t) and X′(t) by exclusive OR gates and shift registers. The signals output from the turbo coder, though not illustrated in FIG. 1, are sequentially applied to a symbol repeater or a puncturer, where they are repeated or punctured the signals output from the turbo coder according to a data rate.
The coded signals are decoded in a turbo decoder, and a structure of the turbo decoder will be described with reference to FIG. 2.
FIG. 2 is a block diagram illustrating a structure of a common turbo decoder. Since the turbo decoder has a recursive structure, an operation of the turbo decoder is also performed recursively, and at each iteration (or each iterative decoding process), a reliability to be used for the next iteration is calculated. Now, a decoding process by the turbo decoder will be described with reference to FIG. 2.
Referring to FIG. 2, the turbo decoder is comprised of a first decoder 211, an interleaver 213, a second decoder 215, and a deinterleaver 217. The signals X(t), Y0(t), Y1(t), Y′0(t) and Y′1(t) output from the turbo coder are applied to the turbo decoder. The X(t) is decoded by the first decoder 211, interleaved by the interleaver 213, and then stored in a RAM (Random Access Memory; not shown) of the interleaver 213. Here, the RAM of the interleaver 213 writes therein data interleaved by the interleaver 213. An output signal of the interleaver 213 is provided to the second decoder 215. The second decoder 215 performs decoding on the Y′0(t) and Y′1(t), and the decoding result of the first decoder 211, stored in the RAM of the interleaver 213.
The resultant data obtained by the second decoder 215 (namely, the decoding result data of the first decoder 211, stored in the RAM of the interleaver 213, and the signals Y′0(t) and Y′1(t) generated by interleaving the initial input signal), becomes decoded data obtained through one complete iteration (or one complete decoding process). The decoded data obtained through first iteration (or first iterative decoding process) is provided to the deinterleaver 217. The deinterleaver 217 writes the decoded data output from the second decoder 215, i.e., the decoded data obtained through first iteration, in a RAM (not shown) of the deinterleaver 217. The decoded data obtained through first iteration, written in the RAM of the deinterleaver 217, is provided to a hard decision block 219. The hard decision block 219 performs hard decision on the data output from the deinterleaver 217, and outputs decoded data.
Though not illustrated, the decoded data output from the hard decision block 219 is provided to a CRC checker. The CRC checker performs CRC checking on the hard decision value. As a result of the CRC checking, if no CRC error is detected, the turbo decoder ends the decoding process without further iterating the decoding process, and then generates an interrupt signal indicating completion of the decoding process. However, if a CRC error is detected, the turbo decoder iterates the turbo decoding process a preset number of times. Here, the number of iterating the decoding process is determined so as not to exceed a time period for which the current frame can be completely decoded before the next frame is received. Further, in FIG. 2, Zk represents data generated by feeding back the output data of the deinterleaver 217, for iterative decoding.
The first decoder 211 and the second decoder 215 have the same decoding scheme, and when realized by hardware, they require a large amount of logic components. Therefore, when the turbo decoder is actually realized by hardware, only one decoder is generally used, and for each iteration, the decoder is used twice.
A turbo decoder for performing turbo decoding by iteratively using a single decoder twice, and a timing diagram of the turbo decoder will be described with reference to FIGS. 3 and 4, respectively.
FIG. 3 is a block diagram illustrating an internal structure of a common turbo decoder having a single decoder. The turbo decoder illustrated in FIG. 3 has a decoder using RESOVA (Register Exchange Soft Out Viterbi Algorithm). The RESOVA is a decoding algorithm for minimizing codeword error probability. Unlike the turbo decoder described in conjunction with FIG. 2, the turbo decoder of FIG. 3 includes a single decoder, i.e., a RESOVA decoder 311. In addition, the turbo decoder includes a data sampler 313 for performing sampling on input data, delays 315 and 317 for delaying output data of the data sampler 313 for a predetermined time, a RESOVA post 319, an interleaver 321, a deinterleaver 323, an output buffer 325, and a CRC checker 327.
Referring to FIG. 3, received data ch—deint—do is applied to the data sampler 313, and the data sampler 313 samples the received data ch—deint—do and provides its output to the RESOVA decoder 311. The RESOVA decoder 311 then decodes an output signal of the data sampler 313 by RESOVA, and provides its output to the interleaver 321 through the RESOVA post 319. The interleaver 321 then writes output data of the RESOVA post 319 in a RAM (not shown) included therein, and provides the data written in its RAM to the data sampler 313. The data sampler 313 then re-samples the output data of the interleaver 321, and provides its output to the RESOVA decoder 311. The RESOVA decoder 311 then decodes the output data of the data sampler 313 by RESOVA, and provides its output to the deinterleaver 323 through the RESOVA post 319. The deinterleaver 323 deinterleaves an output signal of the RESOVA post 319, and writes the deinterleaved data in a RAM (not shown) thereof, completing one iteration. The data written in the RAM of the deinterleaver 323 is buffered in the output buffer 325. Further, the data written in the RAM of the deinterleaver 323 is subject to CRC checking in the CRC checker 327. As a result of the CRC checking, if no CRC error is detected, the turbo decoder ends the decoding process without further iterating the decoding, and then generates an interrupt signal indicating completion of the decoding process. However, if a CRC error is detected by the CRC checker 327, the turbo decoder iterates the decoding process a preset number of times. Here, the number of iterating the decoding process is determined so as not to exceed a time period for which the current frame can be completely decoded before the next frame is received.
Next, operation timing of the turbo decoder illustrated in FIG. 3 will be described with reference to FIG. 4.
FIG. 4 is a timing diagram illustrating operation timing of the turbo decoder shown in FIG. 3. In the timing diagram of FIG. 4, one complete decoding process is performed through two iterative decoding processes. In FIG. 4, “DEC1” represents a period where a first decoding process is performed, and “DEC2” represents a period where a second decoding process is performed. Further, it is noted in FIG. 4 that a period where data is written in the RAM of the interleaver is identical to a period where data is written in the RAM of the deinterleaver. That is, an operation of writing data in the RAM of the interleaver and an operation of reading data in the RAM of the deinterleaver are performed simultaneously. Therefore, the interleaver and the deinterleaver must be realized with separate logics and memories. This means that in the decoding process, an operation of writing data in the interleaver memory and at the same time, reading data stored in the deinterleaver memory, or an operation of writing data in the deinterleaver memory and at the same time, reading data stored in the interleaver memory cannot be supported by a single hardware structure, i.e., a general logic and memory structure operating in response to a single clock.
However, it can be noted that the operation of writing data in each memory of the interleaver and the deinterleaver and the operation of reading data stored in the memory are exclusive. This will be described with reference to FIGS. 5A and 5B.
FIG. 5A is a timing diagram illustrating operations of an interleaver and a deinterleaver during an odd-numbered decoding process by the turbo decoder of FIG. 3.
Referring to FIG. 5A, a process of writing data in the memory, or RAM of the interleaver 321 and reading data stored in the memory of the deinterleaver 323 is performed in an odd-numbered decoding process of the turbo decoder. Here, a synchronous SRAM (Static RAM) is typically used for the memories of the interleaver 321 and the deinterleaver 323. In the timing diagram of FIG. 5A, there exists a time lag (or delay) L, caused by the RESOVA decoder 311, between an operation of writing data in the memory of the interleaver 321 and an operation of reading data stored in the memory of the deinterleaver 323.
For both the operation of writing data in the memory of the interleaver 321 and the operation of reading data stored in the memory of the deinterleaver 323, memory addresses are sequentially generated. That is, during writing, data is sequentially written in the memory of the interleaver 321 by increasing the address one by one beginning at an address #0 (or “A”). Likewise, during reading, data is sequentially read from the memory of the deinterleaver 323 by increasing the address one by one beginning at an address #0. Therefore, the data to be read is not damaged by the writing operation.
Next, an even-numbered decoding process by the turbo decoder of FIG. 3 will be described with reference to FIG. 5B.
FIG. 5B is a timing diagram illustrating operations of an interleaver and a deinterleaver during an even-numbered decoding process by the turbo decoder of FIG. 3.
Referring to FIG. 5B, a process of reading data stored in the memory, or RAM of the interleaver 321 and writing data in the memory of the deinterleaver 323 is performed in an even-numbered decoding process of the turbo decoder. Here, a synchronous SRAM is typically used for the memories of the interleaver 321 and the deinterleaver 323. In the timing diagram of FIG. 5B, there exists a time delay L, caused by the RESOVA decoder 311, between an operation of reading data stored in the memory of the interleaver 321 and an operation of writing data in the memory of the deinterleaver 323.
For both the operation of reading data stored in the memory of the interleaver 321 and the operation of writing data in the memory of the deinterleaver 323, memory addresses are generated in the same order. Therefore, as described in conjunction with FIG. 5A, the data to be read is not damaged by the writing operation. However, unlike the odd-numbered decoding process, the even-numbered decoding process does not sequentially generate the memory addresses.
As described above, the turbo decoder includes an interleaver and a deinterleaver for performing decoding on the received data, and the interleaver and the deinterleaver include separate memories for iterative data writing and reading, causing a reduction in efficiency of the hardware logic and memory. For a improvement of a reduction in efficiency of the hardware logic and memory, there have been demands for a definition of new operation timing for the interleaving and deinterleaving operations of the turbo decoder.